package huawei.dfs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

/**
 * 添加与搜索单词 - 数据结构设计
 * hashMap存储子节点,优化为数组
 */
public class WordDictionary {
    private final TreeNode root;

    private static class TreeNode {
        boolean end;
        TreeNode[] children;

        public TreeNode() {
            children = new TreeNode[26];
        }

    }

    public WordDictionary() {
        root = new TreeNode();
    }

    public void addWord(String word) {
        if (word == null || word.length() == 0) {
            return;
        }
        addWord(word, root, 0);
    }

    private void addWord(String word, TreeNode node, int index) {
        char c = word.charAt(index);
        TreeNode next = node.children[c-'a'];
        if (next == null) {
            next = new TreeNode();
            node.children[c-'a']=next;
        }
        if (index + 1 == word.length()) {
            next.end = true;
            return;
        }
        addWord(word, next, index + 1);
    }

    public boolean search(String word) {
        if (word == null || word.length() == 0) {
            return false;
        }
        return search(word, root, 0);
    }

    private boolean search(String word, TreeNode node, int index) {
        char c = word.charAt(index);
        if (c == '.') { // 点表示通配符
            for (TreeNode e :
                    node.children) {
                if(e==null){
                    continue;
                }
                // 最后一个字符,则寻找子节点有无终止节点
                if (index + 1 == word.length()) {
                    if (e.end) {
                        return true;
                    }
                } else {
                    // 非结束,遍历所有子树,看有无符合数据
                    if (search(word, e, index + 1)) {
                        return true;
                    }
                }
            }
            return false;
        }
        TreeNode next = node.children[c-'a'];
        if (next == null) {
            return false;
        }
        if (index + 1 == word.length()) {
            return next.end;
        }
        return search(word, next, index + 1);
    }

    public static void main(String[] args) {
        WordDictionary wordDictionary = new WordDictionary();
        wordDictionary.addWord("bad");
        wordDictionary.addWord("dad");
        wordDictionary.addWord("mad");
        System.out.println(wordDictionary.search("pad")); // return False
        System.out.println(wordDictionary.search("bad")); // return True
        System.out.println(wordDictionary.search(".ad")); // return True
        System.out.println(wordDictionary.search("b..")); // return True

    }

}
